package com.demo.java.OD451_500.OD469;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【根据 IP 查找城市(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146353080
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入
        String cityInfo = scanner.nextLine().trim();  // 读取城市信息
        String[] ipList = scanner.nextLine().trim().split(",");  // 读取查询的IP列表

        // 输出结果
        String result = findBestMatch(cityInfo, ipList);
        System.out.println(result);

        scanner.close();
    }

    // 计算最佳匹配城市的函数
    public static String findBestMatch(String cityInfo, String[] ipList) {
        Map<String, List<IPRange>> cityIPMap = new HashMap<>();

        // 解析城市信息
        String[] cityList = cityInfo.split(";");
        for (String cityItem : cityList) {
            String[] parts = cityItem.split("=");
            String city = parts[0];  // 城市名称
            String ipRange = parts[1];  // IP地址范围
            String[] ipRangeList = ipRange.split(",");  // 分割成多个IP段
            List<IPRange> rangeList = new ArrayList<>();

            // 将每个IP段存入列表
            for (int i = 0; i < ipRangeList.length; i += 2) {
                rangeList.add(new IPRange(ipRangeList[i], ipRangeList[i + 1]));
            }

            // 将城市及其IP段信息存入map
            cityIPMap.put(city, rangeList);
        }

        // 处理查询 IP 列表
        StringBuilder result = new StringBuilder();
        for (String ip : ipList) {
            String bestMatchCity = "";
            int bestMatchLength = Integer.MAX_VALUE;

            // 遍历城市及对应的IP段
            for (Map.Entry<String, List<IPRange>> entry : cityIPMap.entrySet()) {
                String city = entry.getKey();
                List<IPRange> ipRanges = entry.getValue();

                for (IPRange range : ipRanges) {
                    // 判断IP是否在该城市的IP段内
                    if (isIPInRange(ip, range.getStart(), range.getEnd())) {
                        int length = ipRangeLength(range.getStart(), range.getEnd());  // 计算该IP段的长度
                        // 如果该IP段比当前最优匹配的IP段更短，或者相等时按字母顺序选择
                        if (length < bestMatchLength || (length == bestMatchLength && city.compareTo(bestMatchCity) < 0)) {
                            bestMatchCity = city;
                            bestMatchLength = length;
                        }
                    }
                }
            }

            // 将匹配的城市加入结果
            result.append(bestMatchCity).append(",");
        }

        // 删除最后一个多余的逗号
        return result.deleteCharAt(result.length() - 1).toString();
    }

    // 判断IP是否在指定的范围内
    public static boolean isIPInRange(String ip, String start, String end) {
        int ipInt = ipToInt(ip);
        int startInt = ipToInt(start);
        int endInt = ipToInt(end);
        return startInt <= ipInt && ipInt <= endInt;
    }

    // 将IP地址转换为整数
    public static int ipToInt(String ip) {
        String[] parts = ip.split("\\.");
        return (Integer.parseInt(parts[0]) << 24) +
                (Integer.parseInt(parts[1]) << 16) +
                (Integer.parseInt(parts[2]) << 8) +
                Integer.parseInt(parts[3]);
    }

    // 计算IP段的长度
    public static int ipRangeLength(String start, String end) {
        return ipToInt(end) - ipToInt(start) + 1;
    }

    // IP范围类
    private static class IPRange {
        private final String start;
        private final String end;

        public IPRange(String start, String end) {
            this.start = start;
            this.end = end;
        }

        public String getStart() {
            return start;
        }

        public String getEnd() {
            return end;
        }
    }
}